#include<iostream>
#include<vector>
using namespace std;


class UnionFind
{
public:
  UnionFind(int n = 10)
  {
    uf.resize(n,-1);
  }
  int FindRoot(int x)
  {
    int root = x;
    while(uf[root] >= 0)
    {
      root = uf[root];
    }
    //优化点1：路径压缩,将沿途的树上的节点的夫节点都改为root位置
    while(uf[x] >= 0)
    {
      int parent = uf[x];
      uf[x] = root;
      x = parent;
    }
    return root;
  }
  void Union(int x1,int x2)
  {
    int root1 = FindRoot(x1);
    int root2 = FindRoot(x2);
    if(root1 != root2)
    {
      //优化点2：将小树挂在大树上
      if(uf[root2] < uf[root1]) //root1才是小树
        ::swap(root1,root2);

      //让root2这棵树(小树)挂在root1上
      uf[root1] += uf[root2];
      uf[root2] = root1;
    }
  }
  bool isSame(int x1,int x2) 
  {
    return FindRoot(x1) == FindRoot(x2);
  }
  size_t size() const
  {
    int count = 0;
    for(auto& x:uf)
    {
      if(x < 0)
        count++;
    }
    return count;
  }

private:
  vector<int> uf;
};


